//题目:
// 在一个火车旅行很受欢迎的国度，你提前一年计划了一些火车旅行。
// 在接下来的一年里，你要旅行的日子将以一个名为 days 的数组给出。每一项是一个从 1 到 365 的整数。

// 火车票有 三种不同的销售方式 ：
// 一张 为期一天 的通行证售价为 costs[0] 美元；
// 一张 为期七天 的通行证售价为 costs[1] 美元；
// 一张 为期三十天 的通行证售价为 costs[2] 美元。
// 通行证允许数天无限制的旅行。 例如，如果我们在第 2 天获得一张 为期 7 天 的通行证，那么我们可以连着旅行 7 天：
// 第 2 天、第 3 天、第 4 天、第 5 天、第 6 天、第 7 天和第 8 天。
// 返回 你想要完成在给定的列表 days 中列出的每一天的旅行所需要的最低消费 。

// 示例 1：
// 输入：days = [1,4,6,7,8,20], costs = [2,7,15]
// 输出：11
// 解释： 
// 例如，这里有一种购买通行证的方法，可以让你完成你的旅行计划：
// 在第 1 天，你花了 costs[0] = $2 买了一张为期 1 天的通行证，它将在第 1 天生效。
// 在第 3 天，你花了 costs[1] = $7 买了一张为期 7 天的通行证，它将在第 3, 4, ..., 9 天生效。
// 在第 20 天，你花了 costs[0] = $2 买了一张为期 1 天的通行证，它将在第 20 天生效。
// 你总共花了 $11，并完成了你计划的每一天旅行。

// 示例 2：
// 输入：days = [1,2,3,4,5,6,7,8,9,10,30,31], costs = [2,7,15]
// 输出：17
// 解释：
// 例如，这里有一种购买通行证的方法，可以让你完成你的旅行计划： 
// 在第 1 天，你花了 costs[2] = $15 买了一张为期 30 天的通行证，它将在第 1, 2, ..., 30 天生效。
// 在第 31 天，你花了 costs[0] = $2 买了一张为期 1 天的通行证，它将在第 31 天生效。 
// 你总共花了 $17，并完成了你计划的每一天旅行。
 
// 提示：
// 1 <= days.length <= 365
// 1 <= days[i] <= 365
// days 按顺序严格递增
// costs.length == 3
// 1 <= costs[i] <= 1000
#include<iostream>
#include<vector>
#include<limits.h>

using namespace std;
//代码
class Solution 
{
    int ret=INT_MAX;
    int arr[365]={0};//记录从days[i]到过完最后一天，所需花费的最少金额
public:
    // void dfs(const vector<int>& days,const vector<int>& costs,int pos,int sum)
    // {
    //     if(pos>=days.size()){
    //         ret=min(ret,sum);
    //         return;
    //     }
    //     //1.买一天的通行证
    //     dfs(days,costs,pos+1,sum+costs[0]);
    //     //2.买七天的通行证
    //     int new_pos=pos;
    //     while(new_pos<days.size() && days[new_pos]-days[pos]<7) new_pos++;
    //     dfs(days,costs,new_pos,sum+costs[1]);
    //     //3.买三十天的通行证
    //     while(new_pos<days.size() && days[new_pos]-days[pos]<30) new_pos++;
    //     dfs(days,costs,new_pos,sum+costs[2]);
    // }

    //dfs返回的是：从days[pos]到旅行结束，所需花费的最小金额
    int dfs(const vector<int>& days,const vector<int>& costs,int pos)
    {
        if(pos>=days.size()) return 0;
        
        if(arr[pos]!=0) return arr[pos]; //状态已经记录，可以直接返回

        int sum=0;
        //1.买一天的通行证
        sum=dfs(days,costs,pos+1)+costs[0];
        //2.买七天的通行证
        int new_pos=pos;
        while(new_pos<days.size() && days[new_pos]-days[pos]<7) new_pos++;
        sum=min(sum,dfs(days,costs,new_pos)+costs[1]);
        //3.买三十天的通行证
        while(new_pos<days.size() && days[new_pos]-days[pos]<30) new_pos++;
        sum=min(sum,dfs(days,costs,new_pos)+costs[2]);

        arr[pos]=sum; //记忆功能

        return sum;
    }
    int mincostTickets(vector<int>& days, vector<int>& costs) 
    {
        //法一：暴搜
        // dfs(days,costs,0,0);
        // return ret;

        //法二：暴搜优化————>记忆化搜索    √
        return dfs(days,costs,0);
    }
};